package backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 77.组合
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * 你可以按 任何顺序 返回答案。
 */
public class combine {
    /**
     * 一刷二刷思路一致，注意细节即可
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        backtrack(n,k,1,list,result);
        return result;
    }
    public void  backtrack(int n, int k, int start,List<Integer> list,List<List<Integer>> result) {
        if(list.size() == k) {
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = start; i <= n; i++) {
            list.add(i);
            backtrack(n,k,i+1,list,result);
            list.remove(list.size()-1);
        }
    }

}
